/// @tags: Sieve Exclusion
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>

using namespace std;

namespace BlueQuantum {

typedef long long ll;

int const N = 1e5 + 5;

int n, maxa, cnt;
int pri[N], mu[N], a[N];
bool vis[N];
ll ans, val;
vector<int> vec[N];

struct Graph {
  struct Edge {
    int v, nxt;
  } e[N << 1];

  int e_cnt, heads[N];

  inline Edge const& operator[](int index) { return e[index]; }
  inline int& operator()(int index) { return heads[index]; }

  inline void add(int u, int v) {
    e[++e_cnt].v = v, e[e_cnt].nxt = heads[u], heads[u] = e_cnt;
  }
} G, V;

int root;

namespace TP {

int siz[N], fa[N], son[N], dep[N], top[N], dfn[N], cnt;

void dfs1(int u) {
  dfn[u] = ++cnt, siz[u] = 1;
  for (int i = G(u), v; i; i = G[i].nxt) {
    if ((v = G[i].v) != fa[u]) {
      fa[v] = u, dep[v] = dep[u] + 1;
      dfs1(v);
      siz[u] += siz[v];
      if (siz[son[u]] < siz[v]) son[u] = v;
    }
  }
}

void dfs2(int u) {
  if (son[u]) top[son[u]] = top[u], dfs2(son[u]);
  for (int i = G(u), v; i; i = G[i].nxt)
    if ((v = G[i].v) != fa[u] && v != son[u]) top[v] = v, dfs2(v);
}

inline int getLCA(int x, int y) {
  while (top[x] != top[y]) dep[top[x]] > dep[top[y]] ? x = fa[top[x]] : y = fa[top[y]];
  return dep[x] < dep[y] ? x : y;
}

inline bool cmp(int x, int y) { return dfn[x] < dfn[y]; }

}  // namespace TP

using TP::dfn;
using TP::getLCA;

namespace VT {

int top, v_cnt;
int stk[N], h[N], siz[N];
bool key[N];

void dfs(int u, int fa) {
  siz[u] = key[u];
  for (int i = V(u), v; i; i = V[i].nxt)
    if ((v = V[i].v) != fa) {
      dfs(v, u);
      siz[u] += siz[v];
      val += (ll)(TP::dep[v] - TP::dep[u]) * siz[v] * (v_cnt - siz[v]);
    }
  return;
}

}  // namespace VT

using VT::h;
using VT::key;
using VT::stk;
using VT::top;
using VT::v_cnt;

void solve(int x) {
  val = v_cnt = top = 0;
  for (int i = x; i <= maxa; i += x)
    for (vector<int>::iterator it = vec[i].begin(); it != vec[i].end(); ++it)
      h[++v_cnt] = *it, key[*it] = true;
  sort(h + 1, h + v_cnt + 1, TP::cmp);
  stk[top = 1] = 1;
  V(1) = 0, V.e_cnt = 0;
  for (int i = 1; i <= v_cnt; ++i) {
    int lca = getLCA(h[i], stk[top]);
    if (lca != stk[top]) {
      while (dfn[lca] < dfn[stk[top - 1]]) V.add(stk[top - 1], stk[top]), --top;
      if (dfn[lca] != dfn[stk[top - 1]]) V(lca) = 0, V.add(lca, stk[top]), stk[top] = lca;
      else
        V.add(lca, stk[top--]);
    }
    V(h[i]) = 0, stk[++top] = h[i];
  }
  for (int j = 1; j < top; ++j) V.add(stk[j], stk[j + 1]);
  VT::dfs(1, 1);
  ans += (ll)val * mu[x];
  for (int i = 1; i <= v_cnt; ++i) key[h[i]] = false;
}

inline void prework() {
  mu[1] = 1;
  for (int i = 2; i <= maxa; ++i) {
    if (!vis[i]) pri[++cnt] = i, mu[i] = -1;
    for (int j = 1; j <= cnt && i * pri[j] <= maxa; ++j) {
      vis[i * pri[j]] = true;
      if (i % pri[j] == 0) break;
      mu[i * pri[j]] = -mu[i];
    }
  }
  TP::top[1] = 1, TP::fa[1] = 1, TP::dep[1] = 1;
  TP::dfs1(1), TP::dfs2(1);
}

inline int main() {
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    maxa = max(maxa, a[i]);
    vec[a[i]].push_back(i);
  }
  for (int i = 1, u, v; i < n; ++i) {
    cin >> u >> v;
    G.add(u, v), G.add(v, u);
  }
  prework();
  for (int i = 1; i <= maxa; ++i)
    if (mu[i]) solve(i);
  cout << ans;
  return 0;
}

}  // namespace BlueQuantum

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("/tmp/CodeTmp/testdata.in", "r", stdin);
  freopen("/tmp/CodeTmp/testdata.out", "w", stdout);
#else
  freopen("Tree.in", "r", stdin);
  freopen("Tree.out", "w", stdout);
#endif
#endif

  ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
  return BlueQuantum::main();
}
